"""
# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
"""

from typing import Optional

class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random


class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        cache = {}
        return self.dfs(head, cache)

    def dfs(self, head: 'Node', cache: 'dict') -> 'Node':
        if head is None:
            return None
        if head in cache:
            return cache[head]
        node = Node(head.val)
        cache[head] = node
        node.next = self.dfs(head.next, cache)
        node.random = self.dfs(head.random, cache)
        return node
        